package cn.edu.zufe.mjt.binary;

/**
 * 对数问题
 * 问题描述：给定一个整数数组 arr 和一个整数 target，要求计算出所有满足 arr[i] - arr[j] = target 的 数对 (i, j) 的数量。
 * 其中 i 和 j 是不同的所用。注意，若 arr[i] 和 arr[j] 的值相同，但位置不同，则算作不同的数对。
 */
public class CoupleNumberQuestions {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int target = 5;
        int sum = countCoupleNumber(arr, target);
        System.out.println(sum);
    }

    /**
     * 因为 target 是定值，因此可以枚举 arr[i]，然后再二分 arr[i] - target 找到 arr[j]，
     * 然后统计 arr[i] 和 arr[j] 不同的数对的数量。
     * 因为数组有序，本质上就是找 arr[j] 的区间，只要找出第一次和最后一次出现的位置，然后计算区间的间隔就得到数量。
     */
    public static int countCoupleNumber(int[] arr, int target) {
        int sum = 0;
        for (int i : arr) {
            int c = i - target;
            int first = BinaryIndexQuestions.binarySearchFirst(arr, c);
            int last = BinaryIndexQuestions.binarySearchLast(arr, c);
            if (first == -1) {
                continue;
            }
            sum += last - first + 1;
        }
        return sum;
    }
}
